package leetcode; /**
 * description:
 * author:张腾
 * date:2021-07-15
 */

import java.util.ArrayDeque;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

/**
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 */
public class leetcode32 {
    public int longestValidParentheses(String s) {
        int max = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i)==')'){
                if (s.charAt(i-1)=='(')
                    dp[i] = (i>=2? dp[i-2]:0)+2;
                else if (i-dp[i-1]>0 && s.charAt(i-dp[i-1]-1)=='(')
                    dp[i] = dp[i-1]+((i-dp[i-1])>=2? dp[i-dp[i-1]-2]:0)+2;

                max = Math.max(max,dp[i]);
            }
        }
        return max;
    }
}
